Submarino


Un submarino tiene n secciones numeradas de 1 al N (1 < N < 101). De estas secciones, algunas se encuentran interconectadas entre sí. Además se sabe que hay un total de e interconexiones y que la sección N es la salida de emergencia.

Subproblema A: Si hubiera un marinero en cada sección, excepto en la salida y si éste tardara una unidad de tiempo en llegar a una sección abyacente, determina cuántos marineros llegarína a la salida de emergencia en menos de t ( 0 < t < 101 ) unidades de tiempo.

Subproblema B: Determina cuántas y cuáles secciones, con excepción de la salida, son críticas. Es decir, qué secciones , independientemente del tiempo t, impedirían que algunos marineros llegaran a la salida de emergencia si estas estuvieran obstruidas.

Entrada
La primera línea del archivo de texto "Input.txt" contiene los eneteros N,e,y t. Las siguientes e líneas contienen, cada una, los números de dos secciones inteconectadas entre si.

Salida
El archivo de texto "Output.txt" deberá contener en su línea el número de marineros que pueden llegar a la salida de emergencia en menos de t unidades de tiempo, el segundo renglón debera indicarla cantidad de  secciones críticas seguida de la lista correspondiente de secciones

input.txt
output.txt
11 13 5
1 3
1 5
1 8
2 7
2 10
3 6
4 6
5 6
6 7
7 9
8 4
9 10
10 11
5
3 6 7 10

 


 

Regresar